/**
	The Minerva Project, DAG Scheduling Tools
	Copyright (C) 2006 Florin Pop & Stefan Bucur

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
 */

package ro.pub.cs.minerva.graph;

import java.util.*;


/**
 * @author Stefan Bucur
 *
 */
public class Graph<N extends GraphNode, L extends GraphLink<N>> {
	
	private HashSet<N> nodes;
	
	private int time = 0;
	
	private class TopologicalSorter implements GraphSearchHandler<N> {
		private List<N> topoNodes;
		
		public TopologicalSorter() {
			topoNodes = new ArrayList<N>(nodes.size());
		}

		public void nodeEnd(GraphSearchInfo<N> info) {
			topoNodes.add(0, info.getNode());
		}

		public void nodeStart(GraphSearchInfo<N> info) {
			// Do nothing
			
		}
		
		public List<N> getResults() {
			return topoNodes;
		}
		
	}
	
	private class CyclicityTester implements GraphSearchHandler<N> {
		private boolean isCyclic = false;
		
		public CyclicityTester() {
			
		}

		public void nodeEnd(GraphSearchInfo<N> info) {
			// Do nothing
			
		}

		public void nodeStart(GraphSearchInfo<N> info) {
			GraphNode node = info.getNode();
			
			for (GraphNode nextNode : node.outLinks.keySet()) {
				if (info.getCurrentColor(nextNode) == GraphSearchInfo.COLOR_GRAY) {
					isCyclic = true;
					
					info.requestStop();
				}
			}
		}
		
		public boolean getResult() {
			return isCyclic;
		}
	}
	
	@SuppressWarnings("unchecked")
	private void doDFS(N crNode, GraphSearchHandler<N> searchHandler) {
		crNode.crColor = GraphSearchInfo.COLOR_GRAY;
		
		crNode.startTime = (++time);
		
		if (searchHandler != null) {
			GraphSearchInfo<N> searchInfo =
				new GraphSearchInfo<N>(crNode, crNode.startTime, (N)crNode.parent);
			searchHandler.nodeStart(searchInfo);
		}
		
		for (GraphNode nextNode: crNode.outLinks.keySet()) {
			if (nextNode.crColor == GraphSearchInfo.COLOR_WHITE) {
				nextNode.parent = crNode;
				
				doDFS((N)nextNode, searchHandler);
			}
		}
		
		crNode.crColor = GraphSearchInfo.COLOR_BLACK;
		
		crNode.endTime = (++time);
		
		if (searchHandler != null) {
			GraphSearchInfo<N> searchInfo =
				new GraphSearchInfo<N>(crNode, crNode.endTime, (N)crNode.parent);
			searchHandler.nodeEnd(searchInfo);
		}
	}
	
	/**
	 * Returns the node whose instance is in the graph node list, and which is
	 * equivalent with a given node.
	 * @param node
	 * @return
	 */
	private N getInstanceEquivalent(N node) {
		for (N crNode: nodes) {
			if (crNode.equals(node))
				return crNode;
			
		}	
		return null;
	}
	

    /*
     * PUBLIC METHODS
     */
	
	/**
	 * 
	 */
	public Graph() {
		nodes = new HashSet<N>();
	}
	
	/**
	 * 
	 * @param node
	 */
	public void addNode(N node) {
		if (node == null)
			throw new GraphException("The node parameter must not be null");
		
		if (nodes.contains(node))
			throw new GraphException("The node is already in the graph");
		
		node.inLinks.clear();
		node.outLinks.clear();
		node.graph = this;
		
		nodes.add(node);
	}
	
	/**
	 * 
	 * @param node
	 */
	public void removeNode(N node) {
		if (!nodes.contains(node))
			throw new GraphException("The node does not exist in the graph");
		
		nodes.remove(this);
		
		node.graph = null;
		
		for (GraphNode crInNode : node.inLinks.keySet()) {
			crInNode.outLinks.remove(node);
		}
		
		node.inLinks.clear();
		
		for (GraphNode crOutNode : node.outLinks.keySet()) {
			crOutNode.inLinks.remove(node);
		}
		
		node.outLinks.clear();
	}
	
	/**
	 * 
	 * @param node
	 */
	public boolean containsNode(N node) {
		return nodes.contains(node);
	}
	
	/**
	 * 
	 * @param link
	 */
	public void addLink(L link) {
		N startNode = link.getStartNode();
		N endNode = link.getEndNode();
		
		if (!(nodes.contains(startNode) &&
				nodes.contains(endNode)))
			throw new GraphException("Both nodes must be in the graph");
		
		if (containsLink(link))
			throw new GraphException("The link already exists");
		
		startNode.outLinks.put(endNode, link);
		endNode.inLinks.put(startNode, link);
	}
	
	/**
	 * 
	 * @param link
	 * @return
	 */
	public boolean containsLink(L link) {
		if (link == null)
			return false;
		
		N startNode = link.getStartNode();
		N endNode = link.getEndNode();
		
		if (!containsNode(startNode) || !containsNode(endNode))
			return false;
		
		return link.equals(startNode.outLinks.get(endNode));
	}
	
	/**
	 * 
	 * @param link
	 */
	public void removeLink(L link) {
		N startNode = link.getStartNode();
		N endNode = link.getEndNode();
		
		if (!(nodes.contains(startNode) &&
				nodes.contains(endNode)))
			throw new GraphException("Both nodes must be in the graph");
		
		if (!containsLink(link))
			throw new GraphException("The link does not exist");
		
		startNode.outLinks.remove(startNode);
		startNode.inLinks.remove(endNode);
	}
	
	public GraphNode[] getNodes() {
		return nodes.toArray(new GraphNode[0]);
	}
	
	public void scanDepthFirst(GraphSearchHandler<N> searchHandler) {
		
		for (N crNode: nodes) {
			crNode.startTime = 0;
			crNode.endTime = 0;
			crNode.crColor = GraphSearchInfo.COLOR_WHITE;
			crNode.parent = null;
		}
		
		time = 0;
		
		for (N crNode: nodes) {
			if (crNode.crColor == GraphSearchInfo.COLOR_WHITE) {
				doDFS(crNode, searchHandler);
			}
		}
	}
	
	public void scanBreadthFirst(GraphSearchHandler<N> searchHandler) {
		
	}
	
	public List<N> topologicalSort() {
		TopologicalSorter sorter = new TopologicalSorter();
		
		scanDepthFirst(sorter);
		
		return sorter.getResults();
	}
	
	public boolean isCyclic() {
		CyclicityTester tester = new CyclicityTester();
		
		scanDepthFirst(tester);
		
		return tester.getResult();
	}
	
	@SuppressWarnings("unchecked")
	public void mergeGraph(Graph<N, L> graph) {
		try {
			for (GraphNode crNode: graph.nodes) {
				GraphNode newNode = crNode;
				
				if (! containsNode((N)crNode)) {
					newNode = (GraphNode)crNode.clone();
					
					this.addNode((N)newNode);
				}
			}
			
			for (GraphNode crNode: graph.nodes)	{
				GraphNode newCrNode = this.getInstanceEquivalent((N)crNode);
				
				for (GraphNode nextNode: crNode.outLinks.keySet()) {
					
					GraphNode newNextNode = this.getInstanceEquivalent((N)nextNode);
					
					if (newCrNode.outLinks.containsKey(newCrNode)) {
						L oldLink = (L)newCrNode.outLinks.get(newNextNode);
						
						this.removeLink(oldLink);
					}
					
					L newLink = (L)crNode.outLinks.get(nextNode).clone();
					
					newLink.startNode = (N)newCrNode;
					newLink.endNode = (N)newNextNode;
					
					this.addLink(newLink);
				}
				
			}
			
		} catch (CloneNotSupportedException ex) {
			throw new GraphException("The graphs cannot be merged", ex);
		}
	}
}
